#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点
typedef struct TreeNode {
    int value;
    struct TreeNode *left, *right;
} TreeNode;

// 创建新节点
TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->value = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 插入节点到二叉排序树
TreeNode* insert(TreeNode* root, int value) {
    if (root == NULL) {
        return createNode(value);
    }
    if (value < root->value) {
        root->left = insert(root->left, value);
    } else {
        root->right = insert(root->right, value);
    }
    return root;
}

// 反向中序遍历，从大到小输出
void reverseInOrder(TreeNode* root) {
    if (root != NULL) {
        reverseInOrder(root->right);  // 遍历右子树
        printf("%d ", root->value);  // 输出根节点
        reverseInOrder(root->left);  // 遍历左子树
    }
}

// 释放树的内存
void freeTree(TreeNode* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

// 主函数
int main() {
    TreeNode* root = NULL;

    // 插入一些值
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 60);
    root = insert(root, 80);

    printf("Binary Search Tree elements from largest to smallest:\n");
    reverseInOrder(root);  // 从大到小输出

    // 释放内存
    freeTree(root);

    return 0;
}
